/**
 * //You are given a string s consisting of lowercase English letters. A duplicate
 * //removal consists of choosing two adjacent and equal letters and removing them.
 * //
 * // We repeatedly make duplicate removals on s until we no longer can.
 * //
 * // Return the final string after all such duplicate removals have been made. It
 * //can be proven that the answer is unique.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: s = "abbaca"
 * //Output: "ca"
 * //Explanation:
 * //For example, in "abbaca" we could remove "bb" since the letters are adjacent
 * //and equal, and this is the only possible move.  The result of this move is that
 * //the string is "aaca", of which only "aa" is possible, so the final string is
 * //"ca".
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: s = "azxxzy"
 * //Output: "ay"
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // 1 <= s.length <= 10⁵
 * // s consists of lowercase English letters.
 * //
 * //
 * // Related Topics 栈 字符串 👍 446 👎 0
 */

package com.xixi.dataStructure.stack;

import java.util.Stack;

public class ID01047RemoveAllAdjacentDuplicatesInString {
    public static void main(String[] args) {
        Solution solution = new ID01047RemoveAllAdjacentDuplicatesInString().new Solution();
        solution.removeDuplicates("abbaca");
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public String removeDuplicates(String s) {
            char[] sChar = s.toCharArray();
            if (sChar.length == 1) return s;

            Stack<Character> stack = new Stack<>();
            stack.push(sChar[0]);

            for (int i = 1; i < sChar.length; i++) {
                if (stack.isEmpty()) {
                    stack.push(sChar[i]);
                    continue;
                }
                Character top = stack.peek();
                if (sChar[i] == top) {
                    stack.pop();
                } else {
                    stack.push(sChar[i]);
                }


            }

            StringBuilder sb = new StringBuilder();
            while (!stack.isEmpty()) {
                sb.append(stack.pop());
            }


            return sb.reverse().toString();

        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}